package leetcode.code0488;

import java.util.HashMap;
import java.util.Map;

public class Solution extends Solution488 {
	// 红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W'
//	private int[] boardSum;
	private int[] hands;
	private int handLen;

	private final int MAX = 6;

	private Map<String, Integer> booms;
	private Map<String, StringBuffer> done;

	private int w;

	private int debug = 0;

	@Override
	public int findMinStep(String board, String hand) {
		this.booms = new HashMap<>();
		this.done = new HashMap<>();
		this.w = MAX;
		StringBuffer boards = this.boards(board);
		this.hands(hand);
		int ans = this.f(boards, handLen);
		return ans == MAX ? -1 : ans;// offset在boards范围尝试hands[]字符串
	}

	private int f(StringBuffer board, int left) {
		if (this.booms.containsKey(board.toString())) {
			return this.booms.get(board.toString());
		}
		if (board.length() == 0) {
			this.w = this.handLen - left;
			return this.handLen - left;
		}
		if (left == 0 || this.handLen - left > this.w) {
			return MAX;
		}
//		System.out.println(this.debug++);
		int ans = MAX;
		for (int i = 0; i < board.length(); i++) {
			for (int j = 0; j < 5; j++) {
				if (this.hands[j] > 0) {
					this.hands[j]--;
					StringBuffer boom = this.boom(board, i, j);
					ans = Math.min(ans, this.f(boom, left - 1));
					this.hands[j]++;
				}
			}
		}
		this.booms.put(board.toString(), ans);
		return ans;
	}

	private StringBuffer boom(StringBuffer board, int left, int c) {
		StringBuffer ans = new StringBuffer(board).insert(left, c);
		if (this.done.containsKey(ans.toString())) {
			return this.done.get(ans.toString());
		}
		while (ans.length() >= 3) {
			char cur = ans.charAt(left);
			int right = left;
			for (int i = left - 1; i >= 0; i--) {
				if (ans.charAt(i) == cur) {
					left = i;
				} else {
					break;
				}
			}
			for (; right < ans.length(); right++) {
				if (ans.charAt(right) != cur) {
					break;
				}
			}
			if (right - left >= 3) {
				ans.delete(left, right);
				if (ans.length() == 0) {
					break;
				}
				left = left >= ans.length() ? left - 1 : left;
			} else {
				break;
			}
		}
		this.done.put(ans.toString(), ans);
		return ans;
	}

	private void hands(String hand) {
		handLen = hand.length();
		this.hands = new int[5];
		for (char c : hand.toCharArray()) {
			this.hands[this.char2int(c)]++;
		}
	}

	private StringBuffer boards(String board) {
		StringBuffer ans = new StringBuffer();
		for (char c : board.toCharArray()) {
			ans.append(this.char2int(c));
		}
		return ans;
	}

	private int char2int(char c) {
		if ('R' == c) {
			return 0;
		}
		if ('Y' == c) {
			return 1;
		}
		if ('B' == c) {
			return 2;
		}
		if ('G' == c) {
			return 3;
		}
		return 4;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug7();
//		so.debug6();
//		so.debug5();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();

//		System.out.println('R' - 'A');
//		StringBuffer s = new StringBuffer("012345");
//		s.insert(0, 'a');
//		s.insert(1, 'b');
//		s.insert(6, 'c');
//		System.out.println(s.toString());
//		System.out.println((int) '1');
//		System.out.println('1' - '0');
//		System.out.println(s.charAt(1));
//		s.delete(1, 2);
//		System.out.println(s.toString());

	}

}
